{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 二叉查找树的实现"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 树的节点\n",
    "class TreeNode(object):\n",
    "    def __init__(self, x=None):\n",
    "        self.val = x\n",
    "        self.left = None\n",
    "        self.right = None\n",
    "        self.father = None\n",
    "        \n",
    "# 二叉查找树\n",
    "class BinarySearchTree(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.root = None\n",
    "        \n",
    "    def init_with_list(self, vals):\n",
    "        if not vals:\n",
    "            return\n",
    "        self.root = TreeNode()\n",
    "        queue = [self.root]\n",
    "        while vals:\n",
    "            node = queue.pop(0)\n",
    "            node.val = vals.pop(0)\n",
    "            node.left = TreeNode()\n",
    "            node.left.father = node\n",
    "            node.right = TreeNode()\n",
    "            node.right.father = node\n",
    "            queue.append(node.left)\n",
    "            queue.append(node.right)\n",
    "        queue = [self.root]\n",
    "        while queue:\n",
    "            node = queue.pop(0)\n",
    "            if node.left:\n",
    "                if not node.left.val:\n",
    "                    node.left = None\n",
    "                else:\n",
    "                    queue.append(node.left)\n",
    "            if node.right:\n",
    "                if not node.right.val:\n",
    "                    node.right = None\n",
    "                else:\n",
    "                    queue.append(node.right)\n",
    "\n",
    "    def find_min(self):\n",
    "        if not self.root:\n",
    "            return None\n",
    "        return self._find_min(self.root)\n",
    "    \n",
    "    def _find_min(self, node):\n",
    "        if not node.left:\n",
    "            return node\n",
    "        return self._find_min(node.left)\n",
    "    \n",
    "    def find_max(self):\n",
    "        if not self.root:\n",
    "            return None\n",
    "        return self._find_max(self.root)\n",
    "    \n",
    "    def _find_max(self, node):\n",
    "        if not node.right:\n",
    "            return node\n",
    "        return self._find_max(node.right)\n",
    "    \n",
    "    def query(self, val):\n",
    "        return self._query(self.root, val)\n",
    "    \n",
    "    def _query(self, node, val):\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.val == val:\n",
    "            return node\n",
    "        if val < node.val:\n",
    "            return self._query(node.left, val)\n",
    "        else:\n",
    "            return self._query(node.right, val)\n",
    "    \n",
    "    def query_first(self, val):\n",
    "        return self._query_first(self.root, val)\n",
    "    \n",
    "    def _query_first(self, node, val):\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.val == val:\n",
    "            while node.left and node.left.val == val:\n",
    "                node = node.left\n",
    "            if node.left:\n",
    "                left_max_node = self._find_max(node.left)\n",
    "                if left_max_node.val == val:\n",
    "                    return left_max_node\n",
    "            return node\n",
    "        if val < node.val:\n",
    "            return self._query_first(node.left, val)\n",
    "        else:\n",
    "            return self._query_first(node.right, val)\n",
    "    \n",
    "    def insert(self, val):\n",
    "        if not self.root:\n",
    "            self.root = TreeNode(val)\n",
    "        else:\n",
    "            self._insert(self.root, val)\n",
    "    \n",
    "    def _insert(self, node, val):\n",
    "        if val <= node.val:\n",
    "            if node.left:\n",
    "                self._insert(node.left, val)\n",
    "            else:\n",
    "                node.left = TreeNode(val)\n",
    "                node.left.father = node\n",
    "                return\n",
    "        else:\n",
    "            if node.right:\n",
    "                self._insert(node.right, val)\n",
    "            else:\n",
    "                node.right = TreeNode(val)\n",
    "                node.right.father = node\n",
    "                return\n",
    "    \n",
    "    def delete(self, node):\n",
    "        if not node:\n",
    "            return\n",
    "        if not node.left and not node.right:\n",
    "            if node == self.root:\n",
    "                self.root = None\n",
    "                return\n",
    "            if node.father.left == node:\n",
    "                node.father.left = None\n",
    "                return\n",
    "            node.father.right = None\n",
    "            return\n",
    "        if not node.right:\n",
    "            if node == self.root:\n",
    "                self.root = node.left\n",
    "                node.left.father = None\n",
    "                return\n",
    "            if node.father.left == node:\n",
    "                node.father.left = node.left\n",
    "                node.left.father = node.father\n",
    "                return\n",
    "            node.father.right = node.left\n",
    "            node.left.father = node.father\n",
    "            return\n",
    "        if not node.left:\n",
    "            if node == self.root:\n",
    "                self.root = node.right\n",
    "                node.right.father = None\n",
    "                return\n",
    "            if node.father.left == node:\n",
    "                node.father.left = node.right\n",
    "                node.right.father = node.father\n",
    "                return\n",
    "            node.father.right = node.right\n",
    "            node.right.father = node.father\n",
    "            return\n",
    "        suc_node = self.find_successor(node)\n",
    "        node.val = suc_node.val\n",
    "        self.delete(suc_node)\n",
    "    \n",
    "    def find_precessor(self, node):\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.left:\n",
    "            return self._find_max(node.left)\n",
    "        while node.father:\n",
    "            if node.father.right == node:\n",
    "                return node.father\n",
    "            node = node.father\n",
    "        return None\n",
    "    \n",
    "    def find_successor(self, node):\n",
    "        if not node:\n",
    "            return None\n",
    "        if node.right:\n",
    "            return self._find_min(node.right)\n",
    "        while node.father:\n",
    "            if node.father.left == node:\n",
    "                return node.father\n",
    "            node = node.father\n",
    "        return None\n",
    "    \n",
    "    def inoder_traversal(self, node):\n",
    "        if not node:\n",
    "            return []\n",
    "        left = self.inoder_traversal(node.left)\n",
    "        right = self.inoder_traversal(node.right)\n",
    "        return left + [node.val] + right\n",
    "    \n",
    "    def to_list(self):\n",
    "        return self.inoder_traversal(self.root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = BinarySearchTree()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.insert(3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[3]"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.insert(9)\n",
    "tree.insert(2)\n",
    "tree.insert(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 9]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.find_min().val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "9"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.find_max().val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree.insert(5)\n",
    "tree.insert(5)\n",
    "tree.insert(5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 5, 5, 5, 5, 9]"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "5"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.find_precessor(tree.query(5)).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.find_precessor(tree.query_first(5)).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([7,\\\n",
    "                     2,8,\\\n",
    "                     1,None,None,10,\\\n",
    "                     None,2,None,None,None,None,9,None,\\\n",
    "                     None,None,None,None,None,None,None,None,None,None,None,None,8,None,None,None,])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 7, 8, 8, 9, 10]"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "7"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = tree.query(8)\n",
    "tree.find_precessor(a).val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[10, 9, 8, 8, 7, 2, 2, 1]\n"
     ]
    }
   ],
   "source": [
    "a = tree.find_max()\n",
    "res = []\n",
    "while a:\n",
    "    res.append(a.val)\n",
    "    a = tree.find_precessor(a)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 2, 7, 8, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "a = tree.find_min()\n",
    "res = []\n",
    "while a:\n",
    "    res.append(a.val)\n",
    "    a = tree.find_successor(a)\n",
    "print(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 7, 8, 8, 10]"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.delete(tree.query(9))\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 7, 8, 10]"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.delete(tree.query(8))\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 7, 8]"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.delete(tree.find_max())\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 2, 7]"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.delete(tree.find_max())\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 2, 7]"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.delete(tree.find_min())\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 230. 二叉搜索树中第K小的元素"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。\n",
    "\n",
    "# 说明：\n",
    "# 你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。\n",
    "\n",
    "# 示例 1:\n",
    "\n",
    "# 输入: root = [3,1,4,null,2], k = 1\n",
    "#    3\n",
    "#   / \\\n",
    "#  1   4\n",
    "#   \\\n",
    "#    2\n",
    "# 输出: 1\n",
    "    \n",
    "# 示例 2:\n",
    "\n",
    "# 输入: root = [5,3,6,2,4,null,null,1], k = 3\n",
    "#        5\n",
    "#       / \\\n",
    "#      3   6\n",
    "#     / \\\n",
    "#    2   4\n",
    "#   /\n",
    "#  1\n",
    "# 输出: 3\n",
    "    \n",
    "# 进阶：\n",
    "# 如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 中序遍历查找\n",
    "def kth_smallest(root, k):\n",
    "    res = None\n",
    "    \n",
    "    def inorder(node):\n",
    "        nonlocal k, res\n",
    "        if not node:\n",
    "            return\n",
    "        inorder(node.left)\n",
    "        k -= 1\n",
    "        if k == 0:\n",
    "            res = node.val\n",
    "            return\n",
    "        inorder(node.right)\n",
    "    \n",
    "    inorder(root)\n",
    "    \n",
    "    return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([3,1,4,None,2])\n",
    "kth_smallest(tree.root, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([5,3,6,2,4,None,None,1])\n",
    "kth_smallest(tree.root, 3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([3])\n",
    "kth_smallest(tree.root, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "kth_smallest(tree.root, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 450. 删除二叉搜索树中的节点"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。\n",
    "# 返回二叉搜索树（有可能被更新）的根节点的引用。\n",
    "\n",
    "# 一般来说，删除节点可分为两个步骤：\n",
    "\n",
    "# 首先找到需要删除的节点；\n",
    "# 如果找到了，删除它。\n",
    "# 说明： 要求算法时间复杂度为 O(h)，h 为树的高度。\n",
    "\n",
    "# 示例:\n",
    "\n",
    "# root = [5,3,6,2,4,null,7]\n",
    "# key = 3\n",
    "\n",
    "#     5\n",
    "#    / \\\n",
    "#   3   6\n",
    "#  / \\   \\\n",
    "# 2   4   7\n",
    "\n",
    "# 给定需要删除的节点值是 3，所以我们首先找到 3 这个节点，然后删除它。\n",
    "\n",
    "# 一个正确的答案是 [5,4,6,2,null,null,7], 如下图所示。\n",
    "\n",
    "#     5\n",
    "#    / \\\n",
    "#   4   6\n",
    "#  /     \\\n",
    "# 2       7\n",
    "\n",
    "# 另一个正确答案是 [5,2,6,null,4,null,7]。\n",
    "\n",
    "#     5\n",
    "#    / \\\n",
    "#   2   6\n",
    "#    \\   \\\n",
    "#     4   7"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def find_min(root):\n",
    "    if not root.left:\n",
    "        return root.left\n",
    "    return find_min(root.left)\n",
    "\n",
    "def delete_node(root, key):\n",
    "    if not root:\n",
    "        return None\n",
    "    if key < root.val:\n",
    "        root.left = delete_node(root.left, key)\n",
    "        return root\n",
    "    if key > root.val:\n",
    "        root.right = delete_node(root.right, key)\n",
    "        return root\n",
    "    # 没有左子树，则直接返回右节点\n",
    "    if not root.left:\n",
    "        return root.right\n",
    "    # 没有右子树，则直接返回左节点\n",
    "    if not root.right:\n",
    "        return root.left\n",
    "    # 同时有左右子树，返回后继节点（右子树的最左叶子）\n",
    "    successor = find_min(root.right)\n",
    "    successor.left = root.left\n",
    "    successor.right = delete_node(root.right, key)\n",
    "    return successor"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 3, 4, 5, 6]"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([5,3,6,2,4,None,7])\n",
    "tree.root = delete_node(tree.root, 7)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1]"
      ]
     },
     "execution_count": 32,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([1])\n",
    "tree.root = delete_node(tree.root, 7)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 33,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([1])\n",
    "tree.root = delete_node(tree.root, 1)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "tree.root = delete_node(tree.root, 1)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 700. 二叉搜索树中的搜索"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定二叉搜索树（BST）的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在，则返回 NULL。\n",
    "\n",
    "# 例如，\n",
    "\n",
    "# 给定二叉搜索树:\n",
    "\n",
    "#         4\n",
    "#        / \\\n",
    "#       2   7\n",
    "#      / \\\n",
    "#     1   3\n",
    "\n",
    "# 和值: 2\n",
    "# 你应该返回如下子树:\n",
    "\n",
    "#       2     \n",
    "#      / \\   \n",
    "#     1   3\n",
    "# 在上述示例中，如果要找的值是 5，但因为没有节点值为 5，我们应该返回 NULL。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 递归搜索\n",
    "def search_BST(root, val):\n",
    "    if not root:\n",
    "        return None\n",
    "    if val < root.val:\n",
    "        return search_BST(root.left, val)\n",
    "    if val > root.val:\n",
    "        return search_BST(root.right, val)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4,2,7,1,3])\n",
    "tree.root = search_BST(tree.root, 2)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4,2,7,1,3])\n",
    "tree.root = search_BST(tree.root, 5)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4])\n",
    "tree.root = search_BST(tree.root, 4)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "tree.root = search_BST(tree.root, 4)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 直接遍历\n",
    "def search_BST2(root, val):\n",
    "    while root:\n",
    "        if val < root.val:\n",
    "            root = root.left\n",
    "        elif val > root.val:\n",
    "            root = root.right\n",
    "        else:\n",
    "            return root\n",
    "    return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3]"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4,2,7,1,3])\n",
    "tree.root = search_BST2(tree.root, 2)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4,2,7,1,3])\n",
    "tree.root = search_BST2(tree.root, 5)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4])\n",
    "tree.root = search_BST2(tree.root, 4)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "tree.root = search_BST2(tree.root, 4)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 701. 二叉搜索树中的插入操作"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "# 给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 保证原始二叉搜索树中不存在新值。\n",
    "\n",
    "# 注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。 你可以返回任意有效的结果。\n",
    "\n",
    "# 例如, \n",
    "\n",
    "# 给定二叉搜索树:\n",
    "\n",
    "#         4\n",
    "#        / \\\n",
    "#       2   7\n",
    "#      / \\\n",
    "#     1   3\n",
    "\n",
    "# 和 插入的值: 5\n",
    "# 你可以返回这个二叉搜索树:\n",
    "\n",
    "#          4\n",
    "#        /   \\\n",
    "#       2     7\n",
    "#      / \\   /\n",
    "#     1   3 5\n",
    "# 或者这个树也是有效的:\n",
    "\n",
    "#          5\n",
    "#        /   \\\n",
    "#       2     7\n",
    "#      / \\   \n",
    "#     1   3\n",
    "#          \\\n",
    "#           4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insert_into_BST(root, val):\n",
    "    if not root:\n",
    "        return TreeNode(val)\n",
    "    if val <= root.val:\n",
    "        root.left = insert_into_BST(root.left, val)\n",
    "    else:\n",
    "        root.right = insert_into_BST(root.right, val)\n",
    "    return root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[1, 2, 3, 4, 5, 7]"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([4,2,7,1,3])\n",
    "tree.root = insert_into_BST(tree.root, 5)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[0, 1, 2, 3, 4, 5, 7]"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree.root = insert_into_BST(tree.root, 0)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[5]"
      ]
     },
     "execution_count": 50,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "tree.root = insert_into_BST(tree.root, 5)\n",
    "tree.to_list()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### LeetCode 938. 二叉搜索树的范围和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定二叉搜索树的根结点 root，返回 L 和 R（含）之间的所有结点的值的和。\n",
    "\n",
    "二叉搜索树保证具有唯一的值。\n",
    "\n",
    " \n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：root = [10,5,15,3,7,null,18], L = 7, R = 15\n",
    "输出：32\n",
    "\n",
    "示例 2：\n",
    "\n",
    "输入：root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10\n",
    "输出：23\n",
    " \n",
    "\n",
    "提示：\n",
    "\n",
    "树中的结点数量最多为 10000 个。\n",
    "最终的答案保证小于 2^31。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [],
   "source": [
    "def range_sum_BST(root, L, R):\n",
    "    if not root:\n",
    "        return 0\n",
    "    if root.val < L:\n",
    "        return range_sum_BST(root.right, L, R)\n",
    "    if root.val > R:\n",
    "        return range_sum_BST(root.left, L, R)\n",
    "    return root.val + range_sum_BST(root.left, L, R) + range_sum_BST(root.right, L, R)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "32"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([10,5,15,3,7,None,18])\n",
    "range_sum_BST(tree.root, 7, 15)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "23"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([10,5,15,3,7,13,18,1,None,6])\n",
    "range_sum_BST(tree.root, 6, 10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "78"
      ]
     },
     "execution_count": 54,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([10,5,15,3,7,13,18,1,None,6])\n",
    "range_sum_BST(tree.root, -99, 99)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "100"
      ]
     },
     "execution_count": 55,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([1]*100)\n",
    "range_sum_BST(tree.root, 1, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 56,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([3,8])\n",
    "range_sum_BST(tree.root, 0, 2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "tree = BinarySearchTree()\n",
    "tree.init_with_list([])\n",
    "range_sum_BST(tree.root, 0, 100)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3(py37)",
   "language": "python",
   "name": "py37"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
